Fraunhofer Institute IAIS – Geospatial Visual Analytics Toolkit
VAST 2008 Challenge
Mini Challenge 4:
Evacuation Traces
Authors and Affiliations:
Natalia Andrienko, Fraunhofer Institute IAIS,
Gennady Andrienko, Fraunhofer Institute IAIS,
Student team: NO
Tool(s):
We used the Geospatial Visual
Analytics Toolkit developed at our institute. The system was developed
evolutionary during more than 10 years; the earlier versions were known as
Descartes (1997-2001) and CommonGIS (2001-2007).
Information about the software
can be found on our web site http://geoanalytics.net/and/;
various techniques and functions have been described in our numerous
publications and in tutorials. The list of publications with the texts of many
of them and the tutorials are also available on our web site.
Specific techniques used: map
display; space-time cube (STC); time filter (also used as display animation
control); dynamic query; spatial filter (rectangular “window”); interactive
grouping and classification; dynamic linking between displays (propagation of
selection and classification); specific computational techniques for
trajectories: spatial clustering, computation of the path length for selected
time intervals, dynamic aggregation by cells of a rectangular grid (in
particular, computing the time spent in a cell), detection of possible
interactions between moving objects. The aggregation takes into account all
kinds of filters and updates the computed values when the filter conditions
change.
Two Page Summary: YES
Two-page summary: and-VAST2008challenge.pdf
ANSWERS:
Traces-1: Where was the device set
off?
Grid cell number of where the
device went off:
(67,31) (column, row)
Short Answer:
Premise 1:
the area where people were most seriously affected is around the position of
the bomb.
Premise 2: the most seriously affected people stopped moving immediately or shortly
after the explosion.
Premise 3: the explosion happened shortly before the evacuation start.
Procedure: (1) We identified the moment of the evacuation start: 372; see detailed answer.
(2) We found the traces of people (further called “casualties”) who
stopped moving shortly after moment 372; see Figure 1.
(3) We excluded the hypothesis about a suicide bomber; see the next answer.
(4) N21 was the only person who moved in the area and left it before moment
372. We selected the cell where N21 spent significant time before leaving
the area and which was close to the earliest casualties but not directly
visible to them (not in their room); see Figure 2.
Figure 1: The
Space-Time Cube (STC) showing the movements in the building after moment 372.
The horizontal plane represents the geographical space (i.e. the floor of the
building); the vertical dimension represents time. The traces of the casualties
are colored in red. The vertical lines mean constant spatial positions, i.e.
absence of movement. The two rightmost red lines correspond to the “earliest”
casualties, i.e. those who stopped moving earlier than the others.
Figure 2: The map shows the movements in the supposed area of explosion and around during time interval [1,371] (selected by means of time filter). The small hollow squares and the larger filled squares mark the starting and ending positions, respectively. The traces of the casualties are shown in red, the traces of the others in green. The graduated circles in some grid cells represent the maximum amounts of time spent in these cells by people who passed them during the interval [1,371] (the times spent and other statistics are automatically re-computed when any filter condition changes). The largest filled circle corresponds to value 49; higher values are represented by hollow circles. This is an effect of focusing on the value subrange [0,49] using the manipulator on the right of the map. The mouse points on the cell (67,31), where the supposed bomber spent 14 time units before moving out of the area. In each of the following cells he spent only from 6 to 8 time units.
Traces-2 Identify potential
suspects and/or witnesses to the event.
Note: Potential suspects and/or witnesses are people who were near the
area just prior to the explosion and exhibit suspicious behavior
List of RFID tag numbers :
21.
Short Answer:
We considered and refuted the hypothesis that the bomb could be set off by one of
the casualties. All but one casualty moved for some time after the explosion;
hence, the explosion could not happen exactly in the location of one of these people.
Only one casualty moved before the explosion and could potentially put the bomb on
his/her way. However, the movement occurred outside the explosion-affected area and
on its periphery whereas the explosion happened, most probably, somewhere in the middle.
The only person who did not move after the explosion (as well as before it) had an
isolated position with respect to all other casualties. The explosion could not
occur in this position as there was an unaffected person between it and the positions
of the other casualties.
The only remaining possibility is that the singular person who moved in the area
and left it before the explosion (N21) set the bomb on his way.
Figure 3: The data
on the map are filtered by means of spatial window (brown frame) and
time filter; the selected time interval is [1,371]. The spatial filter
limits the view to only the trajectories having points inside the frame.
The yellowish cell coloring marks the possible area of the explosion.
The traces of the people involved in the incident are in different colors;
see the legend on the left. The trajectory of the supposed bomber Ramon Katalanow
(N21) is in orange. Before the explosion Ramon Katalanow visited the room of
Gale Welsh (red) and Lottie Staley (pink) and then left the area of the explosion.
At moment 371 Ramon Katalanow was at the right end of the corridor where the
explosion evidently happened. He might activate the bomb from there by means of
a remote control.
Figure 4: The map
display shows the movements of people in the explosion area and nearby after
moment 372 (the time interval [372,837] is selected by means of the time
filter). All casualties except Francisco Salter (dark blue) made some movements
after the explosion. 3 people (thin greenish lines) passed by Francisco Salter
after the explosion and successfully moved out; hence the explosion was not in
this place. Gale Welsh (red) and Lottie Staley (pink) were the “earliest”
casualties as they stopped moving earlier than the others. At moment 372 Ramon
Katalanow was at the right end of the corridor where the explosion might
happen. From this place, he moved first to the south but then returned back
(possibly, to look what was going on in the corridor) and went to the east.
Traces-3 Identify any suspects
and/or witnesses who managed to escape the building.
List of RFID tag numbers :
21 (primary incident)
28 (secondary incident)
Short Answer:
If the
space on the east (on the right) of the explosion area can be interpreted
as an exit, then the supposed bomber Ramon Katalanow (N21)
managed to escape the building. The trace of Ramon Katalanow after the
explosion is shown in orange on the map in Figure 4. The orange-filled square
marks his final position.
We also detected an area on the northeast where a secondary incident evidently
happened in the interval [550,580]; see the detailed answer.
N28 (Cecil Dennison) was among the last who left the area; his/her behavior
before and after that were rather suspicious. N28, most probably, escaped, but
he/she moved to a separate place instead of joining other people.
Figure 5: The
movements on the northeast of the building before the supposed time of the
secondary incident. In violet are the traces of the probable casualties, who
stopped moving after moment 580 (latest by moment 668). In red is the trace of
Cecil Dennison (N28),
Figure 6: The
movements in the same area after moment 550. After this moment nobody passed
through the northeastern door. The supposed casualties (in violet) mostly moved
away from the door before finally stopping. Cecil Dennison (N28, in red) did
not go to the same place (supposed exit) where the other people (in green) did.
Traces-4 Identify any
casualties.
List of RFID tag numbers :
18; 19; 50; 56; 76; (+ 36 if not an error in data) – victims of the
primary incident (occurred at about moment 370)
47, 60, 65, 69, 78; 39 (a bit later) – victims of a secondary incident
(occurred in the interval from 550 to 580)
59 – possibly injured in a crowd (stopped moving by moment 693)
Short Answer:
We assumed
that casualties are the people whose traces end in the interior part of the
building rather than in one of the areas near the outer walls, which can be
interpreted as exits or safe areas. Using the map and STC, we have detected two
groups of people who stopped moving in different areas in time intervals
[372,440] and [581,621]. We interpreted the first group as the victims of the
primary incident (explosion), which happened approximately at moment 370.
However, N36 (Francisco Salter; dark blue square in Figures 3 and
4) did not move during the whole time span, which may be an error in the data.
The second group might be victims of another incident, which happened after the
evacuation began (see previous answer). N59 (Olive Palmer) stopped moving by
moment 693 in the middle of the southern corridor; further analysis is given in
the detailed answer.
Figure 7: On the map, the traces of the people who, evidently, managed to
escape, are shown in light greenish color. The traces of the casualties are
shown in red (the first group, who stopped moving in the interval [372,440]),
orange (the second group, who stopped moving mainly in the interval [581,621]
and one person by moment 668), and pink (one person who stopped moving by
moment 693).
Figure 8: The table view shows the computed
lengths of the paths made by the people after moments 440, 621, and 693. The
colors have the same meaning as in the map in Figure 7. All people from the “red”
group did not move after moment 440; all but one person from the “orange” group
stopped moving by moment 621 (the remaining person by moment 668); Olive Palmer
(pink) stopped moving by moment 693.
Traces-5 Describe the
evacuation
Detailed Answer:
We started the analysis with an
overview of the temporal development of the situation by means of an animated
map and a Space-Time Cube (STC). Both visualizations showed us that all but a
few people present in the building were staying in their rooms without movement
till approximately moment 372. At this moment, some people started moving, and
with the passage of time, more and more people were moving. It was hard to
determine precisely the moment when the evacuation began with the use of only
visual techniques. We applied a specific computational technique: for each
trajectory, it computes the traveled paths for consecutive time intervals of
equal length. The resulting time series can be visualized by means of time
graph and time histogram, which shows value frequencies by time intervals.
Figure 9: The time graph (upper panel)
and time histogram (lower panel) visualize the lengths of the paths made by all
people during consecutive time intervals of length 100 starting from [1,100]
and ending with [701,800] plus the interval [801,837] of the length 37. The
labels along the time axis denote the ends of the intervals.
Figure 9 shows us an overview of the situation development during the whole time span from moment 1 to 837 by time intervals of the length 100. For obtaining the time histogram in the lower part of the display, we have divided the value range of the computed attribute ”Path length” into intervals by setting the breaks 0.1, 1, 5, 10, and 15. A color shade has been assigned to each interval. Light yellow stands for the path lengths from 0 to 0.1, which practically means absence of movement. The shades of blue represent non-zero path lengths; darker shades signify higher values. The bars in the time histogram correspond to the time intervals; the heights of the bar segments are proportional to the frequencies of the path length values from the specified value intervals. Pointing with the mouse on a bar segment activates a popup window listing the objects represented by this segment.
From this visualization we can
learn that most people did not move or made very small movements during the
first three intervals, which is signified by the dominance of yellow and
small amounts of light blue in the respective bars. During the fifth and sixth
intervals, i.e. [401,500] and [501,600], almost all people intensively moved,
which is signified by the dominance of dark blue. In the interval [301,400] the
frequency distribution of the path lengths significantly differs from those in
the previous and in the next interval. We can conclude that the evacuation
began during this interval. As not all people began moving simultaneously, the
lengths of the paths vary quite much.
We considered the time interval
[301,400] in more detail by dividing it into sub-intervals of the length 10,
computing the path lengths, and applying the same visualization technique as in
Figure 9. In this way, we found that the first significant change in the number
of moving people occurred in the sub-interval [371,380]. Then, we applied the
same procedure to 1-unit length time intervals starting from [365,366] and
ending with [380,381] (we extended the interval [371,380] to [365,381] in order
to see a longer history). The time histogram in Figure 10 shows that the number
of moving people (represented by blue-shaded segments) noticeably increased in
comparison to the previous intervals first in the interval [372,373] and then
continued increasing through the next intervals. Hence, moment 372 can be taken
as the starting moment of the evacuation. The explosion happened, evidently,
before moment 372, i.e. not later than moment 371.
Figure 10: The display visualizes the lengths of the paths made
during 1-unit length time intervals starting from [365,366] and ending with
[380,381].
We explored the evacuation routes
of the people and their destinations using the map display. In Figure 11 we have
applied spatial clustering of the trajectories according to the closeness of
their end positions. The member trajectories of each cluster are shown in a
specific color. Note that the small hollow squares mark the start positions and
the bigger filled squares mark the end positions of the trajectories. In Figure 11,
the ends of the trajectories are concentrated in four areas near the outer walls
(we shall call them “orange”, “red”, “blue”, and “green” areas); we guess
that these are exits or safe places. The sizes of the clusters show how many people
came to each place. The trajectories colored in magenta end in an area that
cannot be interpreted as an exit or safe place: first, it is in the interior part
of the building, second, many people (green tracks) passed it and moved elsewhere.
Hence, something bad might happen with the people to whom the tracks in magenta
belong, such that they could not reach a safe place. 12 trajectories have been
classified as “noise”, which means that their ends are distant from the ends of
the other trajectories.
Figure 11: A map display with the evacuation routes clustered
according to the end positions.
We separately explored the routes
of the people who did not come to the supposed exits or safe places, i.e.
“noise” (colored in gray) and cluster 5 (magenta). We identified a group of
direct victims of the explosion (see answers 1 and 4), who stopped moving
shortly after moment 372. Then we focused on cluster 5. Using the STC and
movable plane, we determined that all its members stopped moving between
moments 581 and 621. To understand what might happen in the area where these
people stopped, we looked at the movements in this area before moment 581 and
at possible contacts (interactions) between the people. To detect the possible
interactions, we used the computational technique that finds positions in
different trajectories such that the spatial and temporal distances between
them are within given thresholds. We took 1 as the spatial threshold and 0
as the temporal threshold. The STC in Figure 12 shows the movements and
interactions that occurred in the explored area during the interval [470,580].
The interactions are shown by dark gray lines connecting corresponding points
from two trajectories.
Figure 12: The movements and interactions that occurred in the area
of possible secondary incident before the time interval [581,621], in which all
members of cluster 5 (magenta) stopped moving.
By interacting with the STC, we could find that Melonie
Waller (N3), Agnes Masters (N51), and Cecil Dennison (N28) were the last who
successfully passed the area. The first two persons belong to the “green”
cluster. N28 belongs to “noise”: he/she did not join the others after
passing the area but moved to a separate place. Shortly before leaving the
area, these three persons were involved in the following interactions:
N28 + N60 ([525,531]); N3 + N28 ([531,534]); N28 + N60 ([534,540]);
N51 + N60 ([540,544]). The map fragment in Figure 13 shows that all these
interactions occurred near the exit from the corridor. N51 and N28 interacted
with N60 (Lavon Lockhart), who belongs to cluster 5 and was the first from the
cluster to stop moving. The trace of N60 is shown in magenta. In the course
of the second interaction with N28, N60 abruptly changed the movement direction
to the opposite (it may be seen both in Figure 12 and in Figure 13). This may
be a significant fact, which makes N28 suspicious.
Figure 13: The interactions of the persons who were the last to leave
the area of the possible secondary incident.
Figure 14 shows the movements of all members of cluster 5
(the traces are colored differently, for a better distinction) staring from
moment 550, when all others left the corridor, till moment 621, when the last
member of cluster 5 stopped moving. The trace of Lavon Lockhart (N60) is in red. It
is notable that all these people were moving away from the exit door before
finally stopping. Hence, we can guess that some incident might happen at the exit
door, which made the people move away. From the three persons who were the last
to leave the area, the most suspicious is Cecil Dennison (N28, light blue
trace in Figure 14), who did not join the others after passing the door but
chose a different way; see also Figures 5, 6.
Figure 14: The movements in the area of possible incident during the
interval [550,621].
Then we investigated the routes of the remaining people who
did not come to any of the four main exit areas. Their traces, in different
colors, can be seen in the map in Figure 15. Lindsey Bowles (N1, green) came by
moment 466 to the place on the east that can be interpreted as one more exit.
Later (by moment 619) the supposed bomber Ramon Katalanow (N21, orange) came to
approximately the same place. Cecil Dennison (N28, light blue) came by moment
594 in the hall on the north east containing the "green" area but preferred
to move to a different corner of the hall. It can be noted that earlier N28
entered a corridor leading to the area of the explosion but then moved back.
By means of controlled animation, we determined that this happened in the
interval [405,472], i.e. after the explosion and the evacuation start.
In that corridor he/she passed by Francisco Salter (N36, dark blue), who did not
move during the whole time. It is unclear whether these facts are significant
Phil Marin (N39, brown) ended his movement by moment 668 in
a place close to the area where people from cluster 5 stopped. The reason may
be the same as for the members of cluster 5. Christopher Winston (N41, violet)
initially chaotically moved in the northwestern corner but then went to the
southwestern exit. He was moving all the time till moment 837 and, probably,
reached the exit after moment 837. The reason for his late coming is the loss
of time at the beginning of the evacuation.
Olive Palmer (N59, red) initially went toward the southwestern
exit but then (at moment 544) turned in the opposite direction. Probably, he/she
could not move forward because of the crowd (Figure 16) and decided to go to another
exit. At moment 572 Olive Palmer turned back to the west but then (moment 592) turned
again to the east. He/she finally stopped in the middle of the corridor at moment 693.
A possible reason could be that N59 was injured in the crowd near the southeastern door
and could not continue moving. Another possible explanation comes from the fact that
Marcelle Vigil (N13) followed N59 from the moment when N59 left the room till the moment
when he/she finally stopped, see Figure 17. Marcelle Vigil could kill or wound Olive
Palmer and then escape.
Figure 15: The traces of the people whose routes end in particular places,
excluding the earlier identified casualties.
Figure 16: The crowd at the southwestern door in the time interval
[534,546], which, probably, made Olive Palmer (red) turn back.
Figure 17: The path of Olive Palmer in STC
(red). Blue line represents the path of a person (Marcelle Vigil) who followed
Olive Palmer from the moment when he/she left the room till the moment when
he/she finally stopped. After that, Marcelle Vigil turned back, passed through the
southwestern door and joined the others. The greenish lines represent the paths
of the other people who also passed through the southwestern door.
In Figure 11, where the evacuation
traces of people are clustered according to the end positions, it may be
noticed that some people from cluster 1 (red) and 4 (blue) behaved unusually.
One person from cluster 4 first came to the “red” area but did not stay there
and instead moved to the “blue” area. Four people from cluster 1 passed through
the southeastern door. Although the “blue” area is very close to this door,
they moved to the “red” area, which is much farther. From the STC in Figure 18
it may be seen that the person from the “blue” cluster arrived to the “red”
area almost at the same time as the four persons from the east and was for some
time together with them before starting to move to the east. We could not find
any plausible explanation to these unusual movement patterns.
Figure 18: Some people from clusters 1 (red) and cluster 4 (light blue) (see Figure 11) behaved differently from the others.